package leetcode.leetcode322;

/**
 * @author czt
 * @version 1.0
 * @since 2025/1/13
 * 零钱兑换
 */
public class Leetcode322 {

    public int coinChange(int[] coins, int amount) {
        // 每次循环找到当前最优解：面值最大的硬币，他凑出的硬币数最少
        int remainder = amount;
        int count = 0;
        for (int coin : coins) {
            while (remainder > coin) {
                remainder -= coin;
                count++;
            }
            if (remainder == coin) {
                remainder = 0;
                count++;
                break;
            }
        }
        if (remainder > 0) {
            return -1;
        } else {
            return count;
        }
    }

}
